//1089. 复写零
//思路：双指针，以栈的思路存放。
//让 top<arrSize 循环，碰见i位置为0的，让top走两步，将复写 0 的位置预留好；i位置不为 0，top走一步；
//当 top>=arrSize 时，i正好走到已经预留好 0 的合适位置；
//最后我们再从数组尾开始存放元素，碰见非零直接存，碰见 0 就存两遍。

//此方法时间复杂度为O(n),空间复杂度为O(1)
//#include <stdio.h>
//void duplicateZeros(int* arr, int arrSize) {
//    int top = 0, i = -1;//i必须从-1开始，如果从0开始，i调整就会放在while循环最后，i就会多加一次
//    while (top < arrSize)
//    {
//        i++;
//        if (arr[i] != 0)
//        {
//            top++;
//        }
//        else
//        {
//            top += 2;
//        }
//    }
//    //考虑top = arrSize+1时，i位置与i-1位置同时为0的情况(top = arrSize+1就说明最后i的位置也是一个0)
//    int j = arrSize - 1;
//    if (top == arrSize + 1)
//    {
//        arr[j] = 0;
//        j--;
//        i--;
//    }
//    //j从数组尾开始存
//    while (j >= 0)
//    {
//        arr[j] = arr[i];
//        j--;
//        if (0 == arr[i])//碰见i位置为0时再存一遍
//        {
//            arr[j] = arr[i];
//            j--;
//        }
//        i--;
//    }
//}
//int main()
//{
//    int arr[] = { 1,0,2,3,0,0,4,5 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    duplicateZeros(&arr, sz);
//    for (int i = 0; i < sz; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    return 0;
//}


//C++版本

#include <vector>
using namespace std;

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int dest = -1, cur = 0, n = arr.size();
        // 1. 找到最后一个数
        while (cur < n)
        {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }
        // 2. 处理边界问题
        if (dest == n)
        {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        // 3. 从后往前复写
        while (cur >= 0)
        {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};